"""
背包问题

    假设张三要去野营，他准备了以下物品：
        物品	    重量	    价值
        水	    3斤	    10
        书	    1斤	    3
        食物	    2斤	    9
        小刀	    3斤	    4
        衣物	    2斤	    5
        手机	    1斤	    10

    每样东西都有相应的价值，可呆呆的他在收拾背包时发现，他的背包 最大容量只有6斤，装不下所有的东西，只能从这堆东西中挑选 组合价值 最高的物品


关键点
    约束条件： 将背包的容量大小(承重)划分成不同容量大小的子背包，计算每个子背包的最大价值

    物品重量不能超过当前背包容量，不可能将重量为 5斤的物品放进容量为 2斤的背包里，机器可不能像人一样会自己识别大小，这看起来可笑的问题确实会发生，得加上判断语句


需组织一个二维数组

                  1   2   3   4   5   6
  水(3, 10)       /   /   10  10  10  10
  书(1, 3)        3   3   10  13  13  13
食物(2, 9)        3   9   12  13  19  22
小刀(3, 4)        3   9   12  13  19  22
衣物(2, 5)        3   9   12  14  19  22
手机(1, 10)       10  13  19  22  24  29
"""
import numpy as np


def dynamic_p():
    """
    只能拿一次物品的情况下

    每个子问题取得一次物品，就不能再取相同的物品，要么这个要么这个，拿了就没
    比如此时 背包容量为6斤，拿了一瓶水后 占用了背包容量3斤，剩余容量为3斤 我要么再拿一本书和一件衣服(1+2)，要么再拿食物和一部手机(2+1)等，不可能再去拿一瓶水
    """

    items = [
        {"name": "水", "weight": 3, "value": 10},
        {"name": "书", "weight": 1, "value": 3},
        {"name": "食物", "weight": 2, "value": 9},
        {"name": "小刀", "weight": 3, "value": 4},
        {"name": "衣物", "weight": 2, "value": 5},
        {"name": "手机", "weight": 1, "value": 10}
    ]  # 物品项
    max_capacity = 6  # 约束条件为 背包最大承重为6
    dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]
    dp = np.array(dp)
    for row in range(1, len(items) + 1):  # row 代表行
        for col in range(1, max_capacity + 1):  # col 代表列
            weight = items[row - 1]["weight"]  # 获取当前物品重量
            value = items[row - 1]["value"]  # 获取当前物品价值
            if weight > col:  # 判断物品重量是否大于当前背包容量
                dp[row][col] = dp[row-1][col]  # 大于直接取上一次最优结果 此时 row-1 代表上一行
            else:
                # 使用内置函数max()，将上一次最优结果 与 当前物品价值+剩余空间可利用价值 做对比取最大值
                dp[row][col] = max(value + dp[row - 1][col - weight], dp[row - 1][col])
    return dp



"""
可重复拿取物品的情况下

先思考一个问题，为什么上面的代码可以不重复拿去？
那是因为，我们是根据 当前物品的价值+剩余空间的价值 来更新最优解，可这个剩余空间价值是通过上一行来获取的，并未加上当前的商品价值，因此只需要加上当前的商品价格作为参考，即在当行获取最优解
"""

if __name__ == '__main__':
    dp = dynamic_p()
    for i in dp:  # 打印数组
        print(i)

    print(dp[-1][-1])  # 打印最优解的价值和

